package com.ls.eightSort;

import static com.ls.eightSort.MaoPaoSort.show;
import static com.ls.eightSort.QuickSort.swap;

/**
 * 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
        int arr[] = {8,9,1,7,2,3,5,4,6,0,10};
        show(arr);
        sort(arr);
        show(arr);

    }

    public static void sort(int arr[]){
        int group = arr.length>>1;
        Integer insertValue;
        // while赋值分组
        while (group>0){
            // 外层循环决定要移几个数,将一个长度为l数组分为n组，则一共要移动的数除了每组第一个不要动，后面都要动，所以要移动的数肯定是l-n个
            for (int i = group; i <arr.length ; i++) {
                // 内层循环为每个数找到插入的位置
                insertValue = arr[i];
                int j = i-group;
                while (j>=0 && insertValue<arr[j]){
                    // 右移动，空出位置
                    swap(arr,j,j+group);
                    j = j-group;
                }
                arr[j+group] = insertValue;
            }
            group = group>>1;
        }
    }
}
